1. Technical Field
The invention concerns a method and an apparatus for calculating a polynomial multiplication. It further concerns a method of encrypting data as well as an encryption unit.
2. Discussion of Related Art
Mobile terminals are making inroads into more and more areas in everyday life. Increasingly more sensitive information is exchanged between mobile terminals or between mobile terminals and stationary communication terminal points. Data exchange is normally protected by encryption mechanisms. Because of the limited resources of mobile terminals however comprehensive use of cryptographic methods is not possible. That applies in particular to the cryptography with public keys (referred to as public key cryptography) which is generally used to provide a secure channel between the communication partners and for the production of digital signatures.
So-called asymmetrical encryption methods are used in public key cryptography. In that case a public key is used for the encryption of data, which for that purpose is notified in accordance with its name to third parties. Decryption of the data encrypted with the public key can only be effected with a private key which only the receiver of the message has. Decryption of the encrypted message with the public key in contrast is practically not possible. The practical impossibility of decryption is due to the asymmetry of the encryption method which uses an encryption algorithm requiring only relatively few computation steps, on the basis of the public key. Decryption which involves a mathematical inversion of the encryption algorithm however, with just knowledge of the public key, requires so many computation steps that the time involved in such an attempt at decryption, even using the most modern and comprehensive computation technology, is practically infinitely great.
Known asymmetrical encryption methods are RSA as well as Diffie-Hellmann methods and the digital signature algorithm DSA which is based thereon.
In recent times elliptic curve cryptography or ECC has been developed to an increased extent. The advantage of ECC over the other specified methods is that it is possible to use shorter keys without reducing the security of encryption. In addition ECC operations are faster than those of the RSA method. An introduction to elliptic curve cryptography is published on the Internet on the following page: http://www.deviceforge.com/articles/AT4234154468.html.
Encryption in ECC is based on the calculation of a product of two operands, which is referred to as “kP”. In that case P is a point on an elliptic curve or EC and k is a large number. “kP” multiplication is based on point doubling and point addition. All EC point operations are based on addition, subtraction, squaring, multiplication and division in a selected Galois field (GF).
Hardware accelerators for cryptography operations with public keys are ideal ways of reducing the calculation time and energy consumption. Direct implementation of cryptographic operations however leads to a relatively large amount of area being required on a chip. That causes greater difficulty in the use of hardware accelerators from economic points of view. The boundary conditions of the design of hardware accelerators are therefore the computation time required, energy consumption and the area required.
Known methods of polynomial multiplication on a polynomial basis are described hereinafter. In that respect firstly polynomial multiplication generally is examined and then known methods of accelerating polynomial multiplication are discussed.
2.1 Polynomial Multiplication
In a Galois field GF(2n) addition and subtraction are XOR operations. Therefore and for greater ease of understanding of the formulae the usual representation of polynomials
      A    ⁡          (      x      )        =                    ∑                  i          =          0                            n        -        1              ⁢                  a        i            ⁢              x        i            is here modified to
      A    ⁡          (      x      )        =                    ⊕                  i          =          0                            n        -        1              ⁢                  a        i            ⁢                        x          i                .            In the context of this application the XOR operation is identified as “⊕”. The symbol “+” always denotes usual addition.
The product of two polynomials
      A    ⁡          (      x      )        =                              ⊕                      i            =            0                                    n          -          1                    ⁢                        a          i                ⁢                  x          i                ⁢                                  ⁢        and        ⁢                                  ⁢                  B          ⁡                      (            x            )                                =                            ⊕                      i            =            0                                    n          -          1                    ⁢                        b          i                ⁢                  x          i                    is the polynomial
                              C          ⁡                      (            x            )                          =                                            A              ⁡                              (                x                )                                      ·                          B              ⁡                              (                x                )                                              =                                                    ⊕                                  i                  =                  0                                                                              2                  ⁢                  n                                -                2                                      ⁢                                          c                i                            ⁢                              x                i                                                                        (        1        )            wherein
            C      i        =                  ⊕                              k            +            1                    =          i                    ⁢                        a          k                ·                  b          i                      ,that is to say:
            c      0        =                  a        0            ·              b        0                        c      1        =                            a          1                ·                  b          0                    ⊕                        a          0                ·                  b          1                      ⋮            c              n        -        1              =                            a                      n            -            1                          ·                  b          0                    ⊕                        a                      n            -            2                          ·                  b          1                    ⊕                          ⁢      …      ⁢                          ⊕                        a          0                ·                  b                      n            -            1                                ⋮            c                        2          ⁢          n                -        3              =                            a                      n            -            1                          ·                  b                      n            -            2                              ⊕                        a                      n            -            2                          ·                  b                      n            -            1                                          c                        2          ⁢          n                -        2              =                  a                  n          -          1                    ·              b                  n          -          1                    
Direct implementation of formula (1) requires n2 partial multiplications and (n−1)2 XOR operations of partial products in order to calculate the coefficients ci. All operands in formula (1) are only one bit long. When using EC B-233 both polynomials A(x) and B(x) are 233 bits long. That signifies that a total of 2332 one-bit partial multiplications and 2322 XOR operations are required.
2.2 Karatsuba-Based Methods of Polynomial Multiplication
For polynomial multiplication with the original Karatsuba method both operands have to be fragmented into two parts of equal length. If the length n of the operands is unequal they must be supplemented by a leading “0”. If ai identifies the i-th bit and ai identifies the i-th segment of the operand A(x), then the operands can be represented as follows:
                                                                        A                ⁡                                  (                  x                  )                                            =                            ⁢                                                a                                      n                    -                    1                                                  ⁢                                                                  ⁢                …                ⁢                                                                  ⁢                                  a                                      n                    2                                                  ⁢                                  a                                                            n                      2                                        -                    1                                                  ⁢                                                                  ⁢                …                ⁢                                                                  ⁢                                  a                  1                                ⁢                                  a                  0                                                                                                        =                            ⁢                                                                    a                                          n                      -                      1                                                        ⁢                                                                          ⁢                  …                  ⁢                                                                          ⁢                                                            a                                              n                        2                                                              ·                                          x                                              n                        2                                                                                            ⊕                                                      a                                                                  n                        2                                            -                      1                                                        ⁢                                                                          ⁢                  …                  ⁢                                                                          ⁢                                      a                    1                                    ⁢                                      a                    0                                                                                                                          =                            ⁢                                                                    a                    1                                    ·                                      x                                          n                      2                                                                      ⊕                                  a                  0                                                                                        (        2        )            
The polynomial B(x) can be represented in the same fashion. The Karatsuba formula for the product C(x)=A(x)·B(x) is
                              C          ⁡                      (            x            )                          =                                            a              0                        ⁢                          b              0                                ⊕                                    [                                                                    a                    0                                    ⁢                                      b                    0                                                  ⊕                                                      a                    1                                    ⁢                                      b                    1                                                  ⊕                                                      (                                                                  a                        0                                            ⊕                                              a                        1                                                              )                                    ⁢                                      (                                                                  b                        0                                            ⊕                                              b                        1                                                              )                                                              ]                        ·                          x                              n                2                                              ⊕                                    a              1                        ⁢                                          b                1                            ·                              x                n                                                                        (        3        )            
The publication by Bailey, D. V.; Paar, C.: Efficient Arithmetic in Finite Field Extensions with Application in Elliptic Curve Cryptography. Journal of Cryptology, vol. 14, no. 3, 153-176. 2001 proposes a method of applying Karatsuba's idea. Hereinafter that method is referred to as Bailey's method. In that method the operands are divided into three parts. Bailey's method requires six partial multiplications of n/3-bit long operands. That method can be combined with the original Karatsuba formula for such operands, the length of which can be divided by six.
US No 2004/0109561 A1 describes a method of multiplying numbers over a Galois field GF (2m). That method involves the use of a recursive algorithm for breaking a product down into a number of sub-products until the remaining magnitude is sufficient to execute a non-recursive algorithm to complete the multiplication. A disadvantage of the method described in that document is its relatively low area efficiency.